public class Solution {
    /* https://leetcode-cn.com/problems/flood-fill/submissions/
     * 图像渲染
     * 深度优先搜索
     * 1.所在位置 涂色
     * 2.找到其上下左右的位置，判断是否涂色
     *
     * */
    public void DFS(int[][] image, int row, int col, int sr, int sc, int oldColor, int newColor) {
        //判断新的位置是否越界
        if (sr >= row || sr < 0 || sc >= col || sc < 0) {
            return;
        }
        //判断需不需要上色
        if (image[sr][sc] != oldColor || image[sr][sc] == oldColor) {
            return;
        }
        //新位置上色
        image[sr][sc] = newColor;
        for (int[] array : nextP) {
            int newSr = sr + array[0];
            int newSc = sc + array[1];
            //判断下一个位置
            DFS(image, row, col, newSr, newSc, oldColor, newColor);
        }
    }

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int row = image.length;
        int col = image[0].length;
        int oldColoer = image[sr][sc];
        DFS(image, row, col, sr, sc, oldColoer, newColor);
        return image;
    }

    /*
     * 标记数组辅助
     *
     * */
    public void DFS2(int[][] image, int row, int col, int sr, int sc, int oldColor, int newColor, boolean[][] book) {
        //判断新的位置是否越界
        if (sr >= row || sr < 0 || sc >= col || sc < 0) {
            return;
        }
        //判断需不需要上色
        if (image[sr][sc] != oldColor || book[sr][sc]) {
            return;
        }
        //新位置上色
        image[sr][sc] = newColor;
        book[sr][sc] = true;
        for (int[] array : nextP) {
            int newSr = sr + array[0];
            int newSc = sc + array[1];
            //判断下一个位置
            DFS2(image, row, col, newSr, newSc, oldColor, newColor, book);
        }
    }

    public int[][] floodFill2(int[][] image, int sr, int sc, int newColor) {
        int[][] move = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int row = image.length;
        int col = image[0].length;
        int oldColoer = image[sr][sc];
        boolean[][] book = new boolean[row][col];
        DFS2(image, row, col, sr, sc, oldColoer, newColor, book);
        return image;
    }
}